/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/permutation-in-string
   @Language: C++
   @Datetime: 19-04-24 17:49
   */

class Solution {
	bool ismatch(unordered_map<char,int> &match, unordered_map<char,int> &dict){
		if(match.size()!=dict.size()) return false;
		for(auto i=match.begin(); i!=match.end(); ++i)
			if(dict.count(i->first)<1 || dict[i->first]!=i->second) return false;
		return true;
	}
public:
	/**
	 * @param s1: a string
	 * @param s2: a string
	 * @return: if s2 contains the permutation of s1
	 */
	bool checkInclusion(string &p, string &s) {
		// write your code here
		unordered_map<char,int> match, dict;
		for(int i=p.length(); i--; dict[p[i]]++);
		for(int i=0; i<s.length(); ++i){
			match[s[i]]++;
			if(i>=p.length()-1){
				if(ismatch(match, dict)) return true;
				match[s[i-p.length()+1]]--;
				if(match[s[i-p.length()+1]]==0) match.erase(s[i-p.length()+1]);
			}
		}
		return false;
	}
};
